package com.lw.leetcode.tree.c;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * 472. 连接词
 *
 * @author liw
 * @version 1.0
 * @date 2022/5/26 17:36
 */
public class FindAllConcatenatedWordsInADict {

    public static void main(String[] args) {
        FindAllConcatenatedWordsInADict test = new FindAllConcatenatedWordsInADict();


        // ["catsdogcats","dogcatsdog","ratcatdogcat"]
//        String[] arr = {"cat", "cats", "catsdogcats", "dog", "dogcatsdog", "hippopotamuses", "rat", "ratcatdogcat"};

        // ["catdog"]
//        String[] arr = {"cat","dog","catdog"};

        // [abde]
        String[] arr = {"abdc","abd","abde", "e"};

        List<String> allConcatenatedWordsInADict = test.findAllConcatenatedWordsInADict(arr);

        System.out.println(allConcatenatedWordsInADict);
    }

    private Node root;

    public List<String> findAllConcatenatedWordsInADict(String[] words) {
        Arrays.sort(words, (a, b) -> Integer.compare(a.length(), b.length()));
        root = new Node();
        List<String> list = new ArrayList<>();
        for (String word : words) {
            boolean b = find(root, word, 0);
            if (b) {
                list.add(word);
            }
            build(root, word, 0);
        }
        return list;
    }

    private boolean find(Node node, String str, int index) {
        if (node == null) {
            return false;
        }
        if (index == str.length()) {
            return node.end;
        }
        Node no = node.arr[str.charAt(index) - 'a'];
        if (no == null) {
            return false;
        }
        if (find(no, str, index + 1)) {
            return true;
        }
        if (no.end) {
            return find(root, str, index + 1);
        }
        return false;
    }

    private void build(Node node, String str, int index) {
        if (str.length() == index) {
            node.end = true;
            return;
        }
        int i = str.charAt(index) - 'a';
        Node no = node.arr[i];
        if (no == null) {
            no = new Node();
            node.arr[i] = no;
        }
        build(no, str, index + 1);
    }

    private static class Node {
        private boolean end = false;
        private Node[] arr = new Node[26];
    }

}
